package com.data.basic.chapter12;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/** 二分搜索树的测试代码    ------> 复杂
 *
 * 递归【自己的理解】：
 *      1.找到终止条件，通常是递归规模最小的一步操作；
 *      2.执行递归    规模量传递  和  操作数
 * Created by wangbing on 2018/5/6.
 */
public class BST<E extends Comparable<E>> {
    /**
     * 添加元素
     * {不包括重复的元素，如果要包括重复元素的话，那么定义：左子树小于等于节点，或者右子树大于等于节点}
     *  将null当成空树
     * @param e
     */
    public void add(E e){
        root = add(root,e);
    }
/**
 * 1.递归终止的条件
 */
// 向以node为根的二分搜索树中插入元素E，递归算法
// 返回插入新节点后二分搜索树的根------->将节点挂在二叉树下
    private Node add(Node node, E e) {
//        1.递归终止的条件
     if (node==null){
         size++;
         return new Node(e);
     }
//      执行递归  重复元素不再添加
        if (e.compareTo(node.e)<0){
           node.left =  add(node.left,e);
        }else if(e.compareTo(node.e)>0){
            node.right = add(node.right,e);
        }
        return node;

    }

    /**
     * 查询元素
     * @param e
     * @return
     */
    public boolean contains(E e){
        return contains(root,e);
    }

    private boolean contains(Node node, E e) {
        if (node==null){// 1.递归终止条件
            return false;
        }
        if (e.compareTo(node.e)==0){//2.操作数和递归量的变化
            return true;
        }else if (e.compareTo(node.e)>0){
            return  contains(node.right,e);
        }else                                   //(e.compareTo(node.e)<0)
             {
            return contains(node.left,e);
        }

    }
/**
 * 二叉树的前序遍历
  */

    public void preOrder(){
        preOrder(root);

    }
/**
 *  前序遍历以node为根的二叉搜索树，递归算法
  */

    private void preOrder(Node node) {
        if (node==null){//1.递归终止条件
            return;
        }
        // 2.递归逻辑
        System.out.println(node.e);
        preOrder(node.left);
        preOrder(node.right);
    }
    /**
     * 前序遍历 ----->非递归算法，栈的应用
     */
    public void preOrderNR(){

        Stack<Node> stack = new Stack<Node>();

        stack.push(root);
        while(!stack.isEmpty()){
            Node cur = stack.pop();
            System.out.println(cur.e);


            // 注意这里的  要右子树先进栈，左子树在进栈
            if (cur.right!=null){
                stack.push(cur.right);
            }

            if (cur.left!=null){
                stack.push(cur.left);
            }
        }


    }

    /**
     * 中序遍历-----》递归
     *
     */
    public void inOrder(){
        inOrder(root);
    }

    private void inOrder(Node node) {
        if (node==null){
            return;
        }
        inOrder(node.left);
        System.out.println(node.e);
        inOrder(node.right);

    }

    /**
     * 非递归的方式   ----->实现中序排序
     */
    public void inOrderNR(){

        if (root==null){return;}
        Stack<Node>  stack=new Stack<Node>();
        while (root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            System.out.println(root.e);
            root = root.right;
        }
    }

    /**
     * 后序遍历
     */

    public void postOrder(){
        postOrder(root);
    }

    /**
     * 后序遍历以node为节点的二分搜索树，递归算法
     *
     * 应用：为二分搜索树释放空间
     * @param node
     */
    private void postOrder(Node node) {
        if (node==null){
            return;
        }
        postOrder(node.left);
        postOrder(node.right);
        System.out.println(node.e);
    }

    /**
     * 层序遍历的实现--------> 队列完成
     */

    public void levelOrder(){
        Queue<Node> queue = new LinkedList<Node>();
        queue.add(root);
        while(!queue.isEmpty()){
            Node cur = queue.remove();
            System.out.println(cur.e);

            if (cur.left!=null){
                queue.add(cur.left);
            }
            if (cur.right!=null){
                queue.add(cur.right);
            }
        }

    }



    /**
     * 二叉搜索树的删除
     * 注意：最大值在最右边，最小值在最左边
     */

    /**
     * 查找最小元素
     * @return
     */
    public E minimum(){
        if (size==0){
            throw new IllegalArgumentException("BST is empty");
        }
       return minimum(root).e;

    }
    /**
     * 查找最大元素
     * @return
     */

    public E maximum(){
        if (size==0){
            throw new IllegalArgumentException("BST is empty");
        }
        return maximum(root).e;
    }

    private Node maximum(Node node) {
        if (node.right==null){
            return node;
        }
        return  maximum(node.right);
    }

    private Node minimum(Node node) {
        // 递归实现链表的最小值
//        if (node.left==null){
//            return node;
//        }
//        return  minimum(node.left);

        // 非递归实现链表的最小值
        Node temp=null;
        while(node!=null){

            if (node.left==null){
                temp = node;
            }
            node = node.left;
        }
        return temp;
    }

    /**
     * 删除二分搜索树的最小元素
     * @return
     */
    public E removeMin(){
        E ret = minimum();
        root = removeMin(root);
        return ret;
    }



    /**
     * 删除掉以node为根的二分搜索树中的最小节点
     * 返回删除节点后新的二分搜索树的根
     */
    private Node removeMin(Node node) {
        if (node.left==null){
            Node rightNode = node.right;
            node.right = null;
            size--;
            return rightNode;// 返回最小元素的右子树
        }
        node.left = removeMin(node.left);// 将最小元素的右孩子直接赋值给最小元素节点的父亲节点
        return node;

    }

    /**
     *  删除二叉搜索树的最大值
     * @return
     */
    public E removeMax(){
        E ret = maximum();
        root = removeMax(root);

        return ret;

    }
    /**
     * 删除掉以node为根的二分搜索树中的最大节点
     * 返回删除节点后新的二分搜索树的根
     */
    private Node removeMax(Node node) {

        if (node.right==null){
            Node leftNode = node.left;
            node.left=null;
            size--;
            return leftNode;

        }
        node.right = removeMax(node.right);
        return node;
    }

    /**
     * 从二分搜索树中删除元素为e的节点
     * @param e
     */
    public void remove(E e){
        root = remove(root,e);

    }
/**
 *   删除以node为根的二分搜索树中值为e的节点，递归算法
 *   返回删除节点后新的二叉树的根
  */

    private Node remove(Node node, E e) {
        if (node == null){
            return null;
        }
        if (e.compareTo(node.e)<0){// 先进行查找，找到待删除的节点
            node.left = remove(node.left,e);
            return node;
        }
        else if(e.compareTo(node.e)>0){
            node.right = remove(node.right,e);
            return node;
        }
        else{//e = node.e   删除节点 ---->分情况讨论
            if (node.left==null){
                Node rightNode = node.right;
                node.right = null;
                size--;
                return rightNode;// 返回右子树
            }
            if (node.right ==null){
                Node leftNode = node.left;
                node.left = null;
                size--;
                return leftNode;// 返回左子树
            }
// 寻找右子树的最小值来替换这里的要删除的节点
            Node successor = minimum(node.right);
            successor.right = removeMin(node.right);
            size++;// removeMin赋值给了successor，所以要加回来
            successor.left = node.left;


            node.left = node.right = null;
            size--;// 删除了节点的联系

            return successor;

        }


    }

    private class Node{
        /**
         * 二分搜索树的节点类
         */
        public E e;
        public Node left,right;

        public Node(E e) {
            this.e = e;
            this.left = null;
            this.right = null;
        }
    }

    private Node root;
    private int size;

    public BST() {
        root = null;
        size=0;
    }

    public int getSize() {
        return size;
    }

    public boolean isEmpty(){
        return size==0;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        generateBSTString(root,0,res);
        return res.toString();
    }
//
    private void generateBSTString(Node node, int depth, StringBuilder res) {
        if (node==null){
            res.append(generateDepthString(depth)+"null\n");
            return;
        }
        // 基于递归的toString方法
        res.append(generateDepthString(depth)+node.e+"\n");
        generateBSTString(node.left,depth+1,res);
        generateBSTString(node.right,depth+1,res);
    }

    private String generateDepthString(int depth) {
        StringBuilder res = new StringBuilder();
        for (int i=0;i<depth;i++){
            res.append("-");
        }
        return res.toString();
    }
}
